package com.shr.code_interview;

public class Solution_25 {
    public static ListNode Merge(ListNode list1,ListNode list2) {
       	ListNode node1 = list1;
       	ListNode node2 = list2;
       	ListNode head = new ListNode(0) ;
       	ListNode tNode = head ;
       	while(node1 != null && node2 != null){
       		if(node1.val < node2.val){
       			tNode.next = node1 ;
       			node1 = node1.next ;
       		}else{
       			tNode.next = node2;
       			node2 = node2.next ;
       		}
       		tNode = tNode.next ;
       	}
       	while(node1 != null){
       		tNode.next = node1 ;
       		node1 = node1.next;
       		tNode = tNode.next ;
       	}
       	while(node2 != null){
       		tNode.next = node2 ;
       		node2 = node2.next;
       		tNode = tNode.next ;
       	}
       	return head.next ;
    }
	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode head1 = node1 ;
		
		ListNode node2 = new ListNode(2);
		ListNode head2 = node2 ;
    	for(int i = 3; i<7; i++){
    		if(i % 2 == 1){
    			node1.next = new ListNode(i) ;
    			node1 = node1.next ;
    		}else{
    			node2.next = new ListNode(i) ;
    			node2 = node2.next ;
    		}
		}
    	
    	ListNode list = Merge(head1,head2);
    	while(list != null){
    		System.out.print(list.val + " ");
    		list = list.next ;
    	}
	}
}
